/*
————————————————
版权声明：本文为CSDN博主「Manu0728」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/GemOrz/article/details/53184721
*/
/*
序列自动机可以O（n）判断一个串是否是另一个串的子串。
大致思想是对于一个串的每个互不相同的子串，在其某一位置的字符只需要
取最靠前的拿一个，比如aaabab,那么子串ab中的a只需要由原串第一个a产生，
b由第一个b产生即可。建立一个类似trie的结构，对原串每一个字符，
添加到trie中时只添加在每种字符的最后一个的后面。判断时顺着跑一遍就好了。
*/
void add(int x){
    par[++rt]=lst[x];
    for(int i=0;i<26;i++)
        // 把所有的转移都执行转移到最后一个字符，有点像并查集的节点转移都指向同一个根
        for(int j=lst[i];j&&!ch[j][x];j=par[j]) ch[j][x]=rt;
    lst[x]=rt;
}